home *** CD-ROM | disk | FTP | other *** search
/ Programming an RTS Game with Direct3D / Programming an RTS Game with Direct3D.iso / Examples / Chapter 10 / Example 10.1 / terrain.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2006-07-15  |  30.4 KB  |  1,113 lines
  1. #include "terrain.h"
  2. #include "camera.h"
  3. #include "mapObject.h"
  4.  
  5. const DWORD TERRAINVertex::FVF = D3DFVF_XYZ | D3DFVF_NORMAL | D3DFVF_TEX2;
  6.  
  7. //////////////////////////////////////////////////////////////////////////////////////////
  8. //                                    PATCH                                                //
  9. //////////////////////////////////////////////////////////////////////////////////////////
  10.  
  11. PATCH::PATCH()
  12. {
  13.     m_pDevice = NULL;
  14.     m_pMesh = NULL;
  15. }
  16. PATCH::~PATCH()
  17. {
  18.     Release();
  19. }
  20.  
  21. void PATCH::Release()
  22. {
  23.     if(m_pMesh != NULL)
  24.         m_pMesh->Release();
  25.     m_pMesh = NULL;
  26. }
  27.  
  28. HRESULT PATCH::CreateMesh(TERRAIN &ter, RECT source, IDirect3DDevice9* Dev)
  29. {
  30.     if(m_pMesh != NULL)
  31.     {
  32.         m_pMesh->Release();
  33.         m_pMesh = NULL;
  34.     }
  35.  
  36.     try
  37.     {
  38.         m_pDevice = Dev;
  39.         m_mapRect = source;
  40.  
  41.         int width = source.right - source.left;
  42.         int height = source.bottom - source.top;
  43.         int nrVert = (width + 1) * (height + 1);
  44.         int nrTri = width * height * 2;
  45.  
  46.         if(FAILED(D3DXCreateMeshFVF(nrTri, nrVert, D3DXMESH_MANAGED, TERRAINVertex::FVF, m_pDevice, &m_pMesh)))
  47.         {
  48.             debug.Print("Couldn't create mesh for PATCH");
  49.             return E_FAIL;
  50.         }
  51.  
  52.         m_BBox.max = D3DXVECTOR3(-10000.0f, -10000.0f, -10000.0f);
  53.         m_BBox.min = D3DXVECTOR3(10000.0f, 10000.0f, 10000.0f);
  54.  
  55.         //Create vertices
  56.         TERRAINVertex* ver = 0;
  57.         m_pMesh->LockVertexBuffer(0,(void**)&ver);
  58.         for(int z=source.top, z0 = 0;z<=source.bottom;z++, z0++)
  59.             for(int x=source.left, x0 = 0;x<=source.right;x++, x0++)
  60.             {
  61.                 MAPTILE *tile = ter.GetTile(x, z);
  62.  
  63.                 D3DXVECTOR3 pos = D3DXVECTOR3(x, tile->m_height, -z);
  64.                 D3DXVECTOR2 alphaUV = D3DXVECTOR2(x / (float)ter.m_size.x, z / (float)ter.m_size.y);        //Alpha UV
  65.                 D3DXVECTOR2 colorUV = alphaUV * 8.0f;                                                    //Color UV
  66.  
  67.                 ver[z0 * (width + 1) + x0] = TERRAINVertex(pos, ter.GetNormal(x, z), alphaUV, colorUV);
  68.  
  69.                 //Calculate bounding box bounds...
  70.                 if(pos.x < m_BBox.min.x)m_BBox.min.x = pos.x;
  71.                 if(pos.x > m_BBox.max.x)m_BBox.max.x = pos.x;
  72.                 if(pos.y < m_BBox.min.y)m_BBox.min.y = pos.y;
  73.                 if(pos.y > m_BBox.max.y)m_BBox.max.y = pos.y;
  74.                 if(pos.z < m_BBox.min.z)m_BBox.min.z = pos.z;
  75.                 if(pos.z > m_BBox.max.z)m_BBox.max.z = pos.z;
  76.             }
  77.         m_pMesh->UnlockVertexBuffer();
  78.  
  79.         //Calculate Indices
  80.         WORD* ind = 0;
  81.         m_pMesh->LockIndexBuffer(0,(void**)&ind);    
  82.         int index = 0;
  83.  
  84.         for(int z=source.top, z0 = 0;z<source.bottom;z++, z0++)
  85.             for(int x=source.left, x0 = 0;x<source.right;x++, x0++)
  86.             {
  87.                 //Triangle 1
  88.                 ind[index++] =   z0   * (width + 1) + x0;
  89.                 ind[index++] =   z0   * (width + 1) + x0 + 1;
  90.                 ind[index++] = (z0+1) * (width + 1) + x0;        
  91.  
  92.                 //Triangle 2
  93.                 ind[index++] = (z0+1) * (width + 1) + x0;
  94.                 ind[index++] =   z0   * (width + 1) + x0 + 1;
  95.                 ind[index++] = (z0+1) * (width + 1) + x0 + 1;
  96.             }
  97.  
  98.         m_pMesh->UnlockIndexBuffer();
  99.  
  100.         //Set Attributes
  101.         DWORD *att = 0, a = 0;
  102.         m_pMesh->LockAttributeBuffer(0,&att);
  103.         memset(att, 0, sizeof(DWORD)*nrTri);
  104.         m_pMesh->UnlockAttributeBuffer();
  105.     }
  106.     catch(...)
  107.     {
  108.         debug.Print("Error in PATCH::CreateMesh()");
  109.         return E_FAIL;
  110.     }
  111.  
  112.     return S_OK;
  113. }
  114.  
  115. void PATCH::Render()
  116. {
  117.     //Draw mesh
  118.     if(m_visible && m_pMesh != NULL)
  119.         m_pMesh->DrawSubset(0);
  120. }
  121.  
  122. //////////////////////////////////////////////////////////////////////////////////////////
  123. //                                    TERRAIN                                                //
  124. //////////////////////////////////////////////////////////////////////////////////////////
  125.  
  126. TERRAIN::TERRAIN()
  127. {
  128.     m_pDevice = NULL;
  129.     m_pMapTiles = NULL;
  130.     m_pVisitedTiles = m_pVisibleTiles = NULL;
  131. }
  132.  
  133. void TERRAIN::Init(IDirect3DDevice9* Dev, INTPOINT _size)
  134. {
  135.     m_pDevice = Dev;
  136.     m_size = _size;
  137.     m_pHeightMap = NULL;
  138.     m_updateSight = true;
  139.  
  140.     if(m_pMapTiles != NULL)    //Clear old maptiles
  141.         delete [] m_pMapTiles;
  142.  
  143.     //Create m_pMapTiles
  144.     m_pMapTiles = new MAPTILE[m_size.x * m_size.y];
  145.     memset(m_pMapTiles, 0, sizeof(MAPTILE)*m_size.x*m_size.y);
  146.  
  147.     //Clear old textures
  148.     for(int i=0;i<m_diffuseMaps.size();i++)
  149.         m_diffuseMaps[i]->Release();
  150.     m_diffuseMaps.clear();
  151.  
  152.     //Load textures
  153.     IDirect3DTexture9* grass = NULL, *mount = NULL, *snow = NULL;
  154.     if(FAILED(D3DXCreateTextureFromFile(Dev, "textures/grass.jpg", &grass)))debug.Print("Could not load grass.jpg");
  155.     if(FAILED(D3DXCreateTextureFromFile(Dev, "textures/mountain.jpg", &mount)))debug.Print("Could not load mountain.jpg");
  156.     if(FAILED(D3DXCreateTextureFromFile(Dev, "textures/snow.jpg", &snow)))debug.Print("Could not load snow.jpg");
  157.     m_diffuseMaps.push_back(grass);
  158.     m_diffuseMaps.push_back(mount);
  159.     m_diffuseMaps.push_back(snow);
  160.     m_pAlphaMap = NULL;
  161.     m_pLightMap = NULL;
  162.  
  163.     //Fog-of-War texture
  164.     if(FAILED(m_pDevice->CreateTexture(256, 256, 1, D3DUSAGE_RENDERTARGET, D3DFMT_A8R8G8B8, D3DPOOL_DEFAULT, &m_pFogOfWarTexture, NULL)))debug.Print("Failed to create texture: m_pFogOfWarTexture");
  165.  
  166.     // Init font
  167.     D3DXCreateFont(m_pDevice, 40, 0, 0, 1, false,  
  168.                    DEFAULT_CHARSET, OUT_DEFAULT_PRECIS, DEFAULT_QUALITY,
  169.                    DEFAULT_PITCH | FF_DONTCARE, "Arial Black", &m_pProgressFont);
  170.  
  171.     Progress("Creating Terrain", 0.0f);
  172.  
  173.     //Load pixel & vertex shaders
  174.     m_dirToSun = D3DXVECTOR3(1.0f, 0.6f, 0.5f);
  175.     D3DXVec3Normalize(&m_dirToSun, &m_dirToSun);
  176.  
  177.     m_terrainPS.Init(Dev, "shaders/terrain.ps", PIXEL_SHADER);
  178.     m_terrainVS.Init(Dev, "shaders/terrain.vs", VERTEX_SHADER);
  179.     m_vsMatW = m_terrainVS.GetConstant("matW");
  180.     m_vsMatVP = m_terrainVS.GetConstant("matVP");
  181.     m_vsDirToSun = m_terrainVS.GetConstant("DirToSun");
  182.  
  183.     m_objectsPS.Init(Dev, "shaders/objects.ps", PIXEL_SHADER);
  184.     m_objectsVS.Init(Dev, "shaders/objects.vs", VERTEX_SHADER);
  185.     m_objMatW = m_objectsVS.GetConstant("matW");
  186.     m_objMatVP = m_objectsVS.GetConstant("matVP");
  187.     m_objDirToSun = m_objectsVS.GetConstant("DirToSun");
  188.     m_objMapSize = m_objectsVS.GetConstant("mapSize");
  189.  
  190.     //Create white material    
  191.     m_mtrl.Ambient = m_mtrl.Specular = m_mtrl.Diffuse  = D3DXCOLOR(0.5f, 0.5f, 0.5f, 1.0f);
  192.     m_mtrl.Emissive = D3DXCOLOR(0.0f, 0.0f, 0.0f, 1.0f);
  193.  
  194.     //Create visited & visible tiles
  195.     if(m_pVisitedTiles)delete [] m_pVisitedTiles;
  196.     if(m_pVisibleTiles)delete [] m_pVisibleTiles;
  197.     m_pVisitedTiles = new bool[m_size.x * m_size.y];
  198.     m_pVisibleTiles = new bool[m_size.x * m_size.y];
  199.     memset(m_pVisitedTiles, false, sizeof(bool)* m_size.x * m_size.y);
  200.     memset(m_pVisibleTiles, false, sizeof(bool)* m_size.x * m_size.y);
  201.  
  202.     Progress("Creating Terrain", 0.4f);
  203.  
  204.     GenerateRandomTerrain(15);
  205. }
  206.  
  207. void TERRAIN::Release()
  208. {
  209.     try
  210.     {
  211.         for(int i=0;i<m_patches.size();i++)
  212.             if(m_patches[i] != NULL)
  213.                 m_patches[i]->Release();
  214.  
  215.         m_patches.clear();
  216.  
  217.         if(m_pHeightMap != NULL)
  218.         {
  219.             m_pHeightMap->Release();
  220.             delete m_pHeightMap;
  221.             m_pHeightMap = NULL;
  222.         }
  223.  
  224.         m_objects.clear();
  225.     }
  226.     catch(...)
  227.     {
  228.         debug.Print("Error in TERRAIN::Release()");
  229.     }
  230. }
  231.  
  232. void TERRAIN::GenerateRandomTerrain(int numPatches)
  233. {
  234.     try
  235.     {
  236.         Release();
  237.  
  238.         //Create two heightmaps and multiply them
  239.         m_pHeightMap = new HEIGHTMAP(m_size, 20.0f);
  240.         HEIGHTMAP hm2(m_size, 2.0f);
  241.         HEIGHTMAP hm3(m_size, 2.0f);
  242.  
  243.         m_pHeightMap->CreateRandomHeightMap(rand()%2000, 1.0f, 0.7f, 7);
  244.         hm2.CreateRandomHeightMap(rand()%2000, 2.5f, 0.8f, 3);
  245.  
  246.         //Load 4 player filter
  247.         hm3.LoadFromFile(m_pDevice, "heightmaps/four_players.jpg");
  248.         hm2.Cap(hm2.m_maxHeight * 0.4f);
  249.  
  250.         *m_pHeightMap *= hm2;
  251.         *m_pHeightMap *= hm3;
  252.         hm2.Release();        
  253.         hm3.Release();
  254.  
  255.         //Add objects
  256.         HEIGHTMAP hm4(m_size, 1.0f);
  257.         hm4.CreateRandomHeightMap(rand()%1000, 5.5f, 0.9f, 7);
  258.  
  259.         for(int y=0;y<m_size.y;y++)
  260.             for(int x=0;x<m_size.x;x++)
  261.             {
  262.                 if(m_pHeightMap->GetHeight(x, y) == 0.0f && hm4.GetHeight(x, y) > 0.7f && rand()%12 == 0)
  263.                     AddObject(0, INTPOINT(x, y));    //Tree
  264.                 else if(m_pHeightMap->GetHeight(x, y) >= 1.0f && hm4.GetHeight(x, y) > 0.9f && rand()%30 == 0)
  265.                     AddObject(1, INTPOINT(x, y));    //Stone
  266.             }
  267.  
  268.         hm4.Release();        
  269.  
  270.         InitPathfinding();
  271.         CreatePatches(numPatches);
  272.  
  273.         CalculateAlphaMaps();
  274.         CalculateLightMap(false);
  275.     }
  276.     catch(...)
  277.     {
  278.         debug.Print("Error in TERRAIN::GenerateRandomTerrain()");
  279.     }
  280. }
  281.  
  282. void TERRAIN::CreatePatches(int numPatches)
  283. {
  284.     try
  285.     {
  286.         //Clear any old patches
  287.         for(int i=0;i<m_patches.size();i++)
  288.             if(m_patches[i] != NULL)
  289.                 m_patches[i]->Release();
  290.         m_patches.clear();
  291.  
  292.         //Create new patches
  293.         for(int y=0;y<numPatches;y++)
  294.         {
  295.             Progress("Creating Terrain Mesh", y / (float)numPatches);
  296.  
  297.             for(int x=0;x<numPatches;x++)
  298.             {
  299.                 RECT r = {x * (m_size.x - 1) / (float)numPatches, 
  300.                         y * (m_size.y - 1) / (float)numPatches, 
  301.                         (x+1) * (m_size.x - 1) / (float)numPatches,
  302.                         (y+1) * (m_size.y - 1) / (float)numPatches};
  303.                         
  304.                 PATCH *p = new PATCH();
  305.                 p->CreateMesh(*this, r, m_pDevice);
  306.                 m_patches.push_back(p);
  307.             }
  308.         }
  309.     }
  310.     catch(...)
  311.     {
  312.         debug.Print("Error in TERRAIN::CreatePatches()");
  313.     }
  314. }
  315.  
  316. void TERRAIN::CalculateAlphaMaps()
  317. {
  318.     Progress("Creating Alpha Map", 0.0f);
  319.  
  320.     //Clear old alpha maps
  321.     if(m_pAlphaMap != NULL)
  322.         m_pAlphaMap->Release();
  323.  
  324.     //Create new alpha map
  325.     D3DXCreateTexture(m_pDevice, 128, 128, 1, D3DUSAGE_DYNAMIC, D3DFMT_A8R8G8B8, D3DPOOL_DEFAULT, &m_pAlphaMap);
  326.  
  327.     //Lock the texture
  328.     D3DLOCKED_RECT sRect;
  329.     m_pAlphaMap->LockRect(0, &sRect, NULL, NULL);
  330.     BYTE *bytes = (BYTE*)sRect.pBits;
  331.     memset(bytes, 0, 128*sRect.Pitch);        //Clear texture to black
  332.  
  333.     for(int i=0;i<m_diffuseMaps.size();i++)
  334.         for(int y=0;y<sRect.Pitch / 4;y++)
  335.             for(int x=0;x<sRect.Pitch / 4;x++)
  336.             {
  337.                 int terrain_x = m_size.x * (x / (float)(sRect.Pitch / 4.0f));
  338.                 int terrain_y = m_size.y * (y / (float)(sRect.Pitch / 4.0f));
  339.                 MAPTILE *tile = GetTile(terrain_x, terrain_y);
  340.  
  341.                 if(tile != NULL && tile->m_type == i)
  342.                     bytes[y * sRect.Pitch + x * 4 + i] = 255;
  343.             }
  344.  
  345.     //Unlock the texture
  346.     m_pAlphaMap->UnlockRect(0);
  347.     
  348.     //D3DXSaveTextureToFile("alpha.bmp", D3DXIFF_BMP, m_pAlphaMap, NULL);
  349. }
  350.  
  351. void TERRAIN::CalculateLightMap(bool allWhite)
  352. {
  353.     try
  354.     {
  355.         //Clear old alpha maps
  356.         if(m_pLightMap != NULL)
  357.             m_pLightMap->Release();
  358.  
  359.         //Create new light map
  360.         D3DXCreateTexture(m_pDevice, 128, 128, 1, D3DUSAGE_DYNAMIC, D3DFMT_A8, D3DPOOL_DEFAULT, &m_pLightMap);
  361.  
  362.         //Lock the texture
  363.         D3DLOCKED_RECT sRect;
  364.         m_pLightMap->LockRect(0, &sRect, NULL, NULL);
  365.         BYTE *bytes = (BYTE*)sRect.pBits;
  366.         memset(bytes, 255, sRect.Pitch*sRect.Pitch);        //Clear texture to white
  367.  
  368.         if(allWhite)
  369.         {
  370.             m_pLightMap->UnlockRect(0);
  371.             return;
  372.         }
  373.  
  374.         for(int y=0;y<sRect.Pitch;y++)
  375.         {
  376.             Progress("Calculating Lightmap", y / (float)sRect.Pitch);
  377.  
  378.             for(int x=0;x<sRect.Pitch;x++)
  379.             {
  380.                 float terrain_x = (float)m_size.x * (x / (float)(sRect.Pitch));
  381.                 float terrain_z = (float)m_size.y * (y / (float)(sRect.Pitch));
  382.  
  383.                 //Find patch that the terrain_x, terrain_z is over
  384.                 bool done = false;
  385.                 for(int p=0;p<m_patches.size() && !done;p++)
  386.                 {
  387.                     RECT mr = m_patches[p]->m_mapRect;
  388.  
  389.                     //Focus within patch maprect or not?
  390.                     if(terrain_x >= mr.left && terrain_x < mr.right &&
  391.                          terrain_z >= mr.top && terrain_z < mr.bottom)
  392.                     {            
  393.                         // Collect only the closest intersection
  394.                         RAY rayTop(D3DXVECTOR3(terrain_x, 10000.0f, -terrain_z), D3DXVECTOR3(0.0f, -1.0f, 0.0f));
  395.                         float dist = rayTop.Intersect(m_patches[p]->m_pMesh);
  396.  
  397.                         if(dist >= 0.0f)
  398.                         {
  399.                             RAY ray(D3DXVECTOR3(terrain_x, 10000.0f - dist + 0.01f, -terrain_z), m_dirToSun);
  400.  
  401.                             for(int p2=0;p2<m_patches.size() && !done;p2++)
  402.                                 if(ray.Intersect(m_patches[p2]->m_BBox) >= 0)
  403.                                 {
  404.                                     if(ray.Intersect(m_patches[p2]->m_pMesh) >= 0)    //In shadow
  405.                                     {
  406.                                         done = true;
  407.                                         bytes[y * sRect.Pitch + x] = 128;
  408.                                     }
  409.                                 }
  410.  
  411.                             done = true;
  412.                         }
  413.                     }
  414.                 }                        
  415.             }
  416.         }
  417.  
  418.         //Smooth lightmap        
  419.         for(int i=0;i<3;i++)
  420.         {
  421.             Progress("Smoothing the Lightmap", i / 3.0f);
  422.  
  423.             BYTE* tmpBytes = new BYTE[sRect.Pitch * sRect.Pitch];
  424.             memcpy(tmpBytes, sRect.pBits, sRect.Pitch * sRect.Pitch);
  425.  
  426.             for(int y=1;y<sRect.Pitch-1;y++)
  427.                 for(int x=1;x<sRect.Pitch-1;x++)
  428.                 {
  429.                     long index = y*sRect.Pitch + x;
  430.                     BYTE b1 = bytes[index];
  431.                     BYTE b2 = bytes[index - 1];
  432.                     BYTE b3 = bytes[index - sRect.Pitch];
  433.                     BYTE b4 = bytes[index + 1];
  434.                     BYTE b5 = bytes[index + sRect.Pitch];
  435.                     
  436.                     tmpBytes[index] = (BYTE)((b1 + b2 + b3 + b4 + b5) / 5);
  437.                 }
  438.  
  439.             memcpy(sRect.pBits, tmpBytes, sRect.Pitch * sRect.Pitch);
  440.             delete [] tmpBytes;
  441.         }
  442.  
  443.         //Unlock the texture
  444.         m_pLightMap->UnlockRect(0);
  445.         
  446.         //D3DXSaveTextureToFile("light.bmp", D3DXIFF_BMP, m_pLightMap, NULL);
  447.     }
  448.     catch(...)
  449.     {
  450.         debug.Print("Error in TERRAIN::CalculateLightMap()");
  451.     }
  452. }
  453.  
  454. D3DXVECTOR3 TERRAIN::GetNormal(int x, int y)
  455. {
  456.     //Neighboring map nodes (D, B, C, F, H, G)
  457.     INTPOINT mp[] = {INTPOINT(x-1, y),   INTPOINT(x, y-1), 
  458.                      INTPOINT(x+1, y-1), INTPOINT(x+1, y),
  459.                        INTPOINT(x, y+1),   INTPOINT(x-1, y+1)};
  460.  
  461.     //if there's an invalid map node return (0, 1, 0)
  462.     if(!Within(mp[0]) || !Within(mp[1]) || !Within(mp[2]) || 
  463.        !Within(mp[3]) || !Within(mp[4]) || !Within(mp[5]))
  464.         return D3DXVECTOR3(0.0f, 1.0f, 0.0f);
  465.  
  466.     //Calculate the normals of the 6 neighboring planes
  467.     D3DXVECTOR3 normal = D3DXVECTOR3(0.0f, 0.0f, 0.0f);
  468.  
  469.     for(int i=0;i<6;i++)
  470.     {
  471.         D3DXPLANE plane;
  472.         D3DXPlaneFromPoints(&plane, 
  473.                             &GetWorldPos(INTPOINT(x, y)),
  474.                             &GetWorldPos(mp[i]), 
  475.                             &GetWorldPos(mp[(i + 1) % 6]));
  476.  
  477.         normal +=  D3DXVECTOR3(plane.a, plane.b, plane.c);
  478.     }
  479.  
  480.     D3DXVec3Normalize(&normal, &normal);
  481.     return normal;
  482. }
  483.  
  484. void TERRAIN::AddObject(int type, INTPOINT mappos)
  485. {
  486.     D3DXVECTOR3 pos = D3DXVECTOR3(mappos.x, m_pHeightMap->GetHeight(mappos), -mappos.y);    
  487.     D3DXVECTOR3 rot = D3DXVECTOR3((rand()%1000 / 1000.0f) * 0.13f, (rand()%1000 / 1000.0f) * 3.0f, (rand()%1000 / 1000.0f) * 0.13);
  488.  
  489.     float sca_xz = (rand()%1000 / 1000.0f) * 0.5f + 0.5f;
  490.     float sca_y = (rand()%1000 / 1000.0f) * 1.0f + 0.5f;
  491.     D3DXVECTOR3 sca = D3DXVECTOR3(sca_xz, sca_y, sca_xz);
  492.  
  493.     m_objects.push_back(OBJECT(type, mappos, pos, rot, sca));
  494. }
  495.  
  496. void TERRAIN::Render(CAMERA &camera)
  497. {
  498.     //Set render states        
  499.     m_pDevice->SetRenderState(D3DRS_LIGHTING, false);
  500.     m_pDevice->SetRenderState(D3DRS_ZWRITEENABLE, true);    
  501.     
  502.     m_pDevice->SetTexture(0, m_pAlphaMap);
  503.     m_pDevice->SetTexture(1, m_diffuseMaps[0]);        //Grass
  504.     m_pDevice->SetTexture(2, m_diffuseMaps[1]);        //Mountain
  505.     m_pDevice->SetTexture(3, m_diffuseMaps[2]);        //Snow
  506.     m_pDevice->SetTexture(4, m_pFogOfWarTexture);        //Lightmap || FogOfWar
  507.     m_pDevice->SetMaterial(&m_mtrl);
  508.  
  509.     D3DXMATRIX world, vp = camera.GetViewMatrix() * camera.GetProjectionMatrix();
  510.     D3DXMatrixIdentity(&world);
  511.     m_pDevice->SetTransform(D3DTS_WORLD, &world);
  512.     
  513.     //Set vertex shader variables
  514.     m_terrainVS.SetMatrix(m_vsMatW, world);
  515.     m_terrainVS.SetMatrix(m_vsMatVP, vp);
  516.     m_terrainVS.SetVector3(m_vsDirToSun, m_dirToSun);
  517.  
  518.     m_terrainVS.Begin();
  519.     m_terrainPS.Begin();
  520.         
  521.     for(int p=0;p<m_patches.size();p++)
  522.         if(!camera.Cull(m_patches[p]->m_BBox))
  523.             m_patches[p]->Render();
  524.  
  525.     m_terrainPS.End();
  526.     m_terrainVS.End();
  527.  
  528.     m_pDevice->SetTexture(1, NULL);
  529.     m_pDevice->SetTexture(2, NULL);
  530.     m_pDevice->SetTexture(3, NULL);
  531.     m_pDevice->SetTexture(4, NULL);
  532.  
  533.     //Render Objects
  534.     m_objectsVS.SetMatrix(m_objMatW, world);
  535.     m_objectsVS.SetMatrix(m_objMatVP, vp);
  536.     m_objectsVS.SetVector3(m_objDirToSun, m_dirToSun);
  537.     m_objectsVS.SetVector3(m_objMapSize, D3DXVECTOR3(m_size.x, m_size.y, 0.0f));
  538.  
  539.     m_pDevice->SetTexture(1, m_pFogOfWarTexture);        //Lightmap
  540.     
  541.     m_objectsVS.Begin();
  542.     m_objectsPS.Begin();
  543.  
  544.     for(int i=0;i<m_objects.size();i++)
  545.         if(!camera.Cull(m_objects[i].m_BBox))
  546.         {
  547.             D3DXMATRIX m = m_objects[i].m_meshInstance.GetWorldMatrix();
  548.             m_objectsVS.SetMatrix(m_objMatW, m);
  549.             m_objects[i].Render();
  550.         }
  551.  
  552.     m_objectsVS.End();
  553.     m_objectsPS.End();
  554. }
  555.  
  556. void TERRAIN::Progress(std::string text, float prc)
  557. {
  558.     m_pDevice->Clear(0, 0, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER, 0xffffffff, 1.0f, 0L);
  559.     m_pDevice->BeginScene();
  560.     
  561.     RECT rc = {200, 250, 600, 300};
  562.     m_pProgressFont->DrawText(NULL, text.c_str(), -1, &rc, DT_CENTER | DT_VCENTER | DT_NOCLIP, 0xff000000);
  563.     
  564.     //Progress bar
  565.     D3DRECT r;
  566.     r.x1 = 200; r.x2 = 600;
  567.     r.y1 = 300; r.y2 = 340;
  568.     m_pDevice->Clear(1, &r, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER, 0xff000000, 1.0f, 0L);
  569.     r.x1 = 202; r.x2 = 598;
  570.     r.y1 = 302; r.y2 = 338;
  571.     m_pDevice->Clear(1, &r, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER, 0xffffffff, 1.0f, 0L);
  572.     r.x1 = 202; r.x2 = 202 + 396 * prc;
  573.     r.y1 = 302; r.y2 = 338;
  574.     m_pDevice->Clear(1, &r, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER, 0xff00ff00, 1.0f, 0L);
  575.  
  576.     m_pDevice->EndScene();
  577.     m_pDevice->Present(0, 0, 0, 0);
  578. }
  579.  
  580. void TERRAIN::SetOrthogonalView()
  581. {
  582.     D3DXMATRIX world, view, proj;
  583.  
  584.     //World matrix
  585.     D3DXMatrixIdentity(&world);
  586.  
  587.     //View matrix (eye & focus in the center of the terrain)
  588.     D3DXVECTOR2 center = D3DXVECTOR2((m_size.x - 1) / 2.0f, -(m_size.y - 1) / 2.0f);
  589.  
  590.     D3DXMatrixLookAtLH(&view, &D3DXVECTOR3(center.x, 1000.0f, center.y),
  591.                               &D3DXVECTOR3(center.x, 0.0f, center.y),
  592.                               &D3DXVECTOR3(0.0f, 0.0f, 1.0f));
  593.  
  594.     //Projection matrix
  595.     D3DXMatrixOrthoLH(&proj, m_size.x-1, m_size.y-1, 0.1f, 2000);
  596.  
  597.     //Set transformation matrices
  598.     m_pDevice->SetTransform(D3DTS_WORLD, &world);
  599.     m_pDevice->SetTransform(D3DTS_VIEW, &view);
  600.     m_pDevice->SetTransform(D3DTS_PROJECTION, &proj);
  601. }
  602.  
  603. void TERRAIN::UpdateSightMatrices(std::vector<MAPOBJECT*> &mapObjects)
  604. {
  605.     memset(m_pVisibleTiles, false, sizeof(bool) * m_size.x * m_size.y);
  606.  
  607.     for(int i=0;i<mapObjects.size();i++)
  608.         if(mapObjects[i] != NULL)
  609.         {
  610.             int sr = mapObjects[i]->m_sightRadius, a = 0;
  611.             INTPOINT start = mapObjects[i]->m_mappos - INTPOINT(sr, sr);
  612.             INTPOINT end = mapObjects[i]->m_mappos + INTPOINT(sr, sr);
  613.  
  614.             for(int y=start.y;y<=end.y;y++)
  615.                 for(int x=start.x;x<=end.x;x++)
  616.                     if(x >= 0 && y >= 0 && x < m_size.x && y < m_size.y)
  617.                     {
  618.                         int index = x + y * m_size.x;
  619.                         m_pVisitedTiles[index] = m_pVisibleTiles[index] = true;
  620.                     }
  621.         }
  622.  
  623.     //Calculate visibility variable of Patches
  624.     for(int i=0;i<m_patches.size();i++)
  625.         if(m_patches[i] != NULL)
  626.         {
  627.             m_patches[i]->m_visible = false;
  628.             RECT r = m_patches[i]->m_mapRect;
  629.  
  630.             for(int y=r.top;y<=r.bottom && !m_patches[i]->m_visible;y++)
  631.                 for(int x=r.left;x<=r.right && !m_patches[i]->m_visible;x++)
  632.                     if(m_pVisitedTiles[x + y * m_size.x])
  633.                         m_patches[i]->m_visible = true;
  634.         }
  635.  
  636.     //Calculate visibility of terrain objects
  637.     for(int i=0;i<m_objects.size();i++)
  638.         m_objects[i].m_visible = m_pVisitedTiles[m_objects[i].m_mappos.x + m_objects[i].m_mappos.y * m_size.x];
  639. }
  640.  
  641. bool TERRAIN::Within(INTPOINT p)
  642. {
  643.     return p.x >= 0 && p.y >= 0 && p.x < m_size.x && p.y < m_size.y;
  644. }
  645.  
  646. void TERRAIN::InitPathfinding()
  647. {
  648.     try
  649.     {
  650.         //Read maptile heights & types from heightmap
  651.         for(int y=0;y<m_size.y;y++)
  652.             for(int x=0;x<m_size.x;x++)
  653.             {
  654.                 MAPTILE *tile = GetTile(x, y);
  655.                 if(m_pHeightMap != NULL)tile->m_height = m_pHeightMap->GetHeight(x, y);
  656.                 tile->mappos = INTPOINT(x, y);
  657.                 
  658.                 if(tile->m_height < 0.3f)         tile->m_type = 0;    //Grass
  659.                 else if(tile->m_height < 7.0f) tile->m_type = 1;    //Stone
  660.                 else                         tile->m_type = 2;    //Snow
  661.             }
  662.  
  663.         //Calculate tile cost as a function of the height variance
  664.         for(int y=0;y<m_size.y;y++)        
  665.             for(int x=0;x<m_size.x;x++)
  666.             {
  667.                 MAPTILE *tile = GetTile(x, y);
  668.  
  669.                 if(tile != NULL)
  670.                 {
  671.                     //Possible neighbors
  672.                     INTPOINT p[] = {INTPOINT(x-1, y-1), INTPOINT(x, y-1), INTPOINT(x+1, y-1),
  673.                                     INTPOINT(x-1, y),                      INTPOINT(x+1, y),
  674.                                     INTPOINT(x-1, y+1), INTPOINT(x, y+1), INTPOINT(x+1, y+1)};
  675.  
  676.                     float variance = 0.0f;
  677.                     int nr = 0;
  678.  
  679.                     //For each neighbor
  680.                     for(int i=0;i<8;i++)    
  681.                         if(Within(p[i]))
  682.                         {
  683.                             MAPTILE *neighbor = GetTile(p[i]);
  684.  
  685.                             if(neighbor != NULL)
  686.                             {
  687.                                 float v = neighbor->m_height - tile->m_height;
  688.                                 variance += (v * v);
  689.                                 nr++;
  690.                             }
  691.                         }
  692.  
  693.                     //Cost = height variance
  694.                     variance /= (float)nr;
  695.                     tile->m_cost = variance + 0.1f;
  696.                     if(tile->m_cost > 1.0f)tile->m_cost = 1.0f;
  697.  
  698.                     //If the tile cost is less than 1.0f, then we can walk on the tile
  699.                     tile->m_walkable = tile->m_cost < 0.5f;
  700.                 }
  701.             }
  702.  
  703.         //Make maptiles with objects on them not m_walkable
  704.         for(int i=0;i<m_objects.size();i++)
  705.         {
  706.             MAPTILE *tile = GetTile(m_objects[i].m_mappos);
  707.             if(tile != NULL)
  708.             {
  709.                 tile->m_walkable = false;
  710.                 tile->m_cost = 1.0f;
  711.             }
  712.         }
  713.  
  714.         //Connect m_pMapTiles using the neightbors[] pointers
  715.         for(int y=0;y<m_size.y;y++)        
  716.             for(int x=0;x<m_size.x;x++)
  717.             {
  718.                 MAPTILE *tile = GetTile(x, y);
  719.                 if(tile != NULL && tile->m_walkable)
  720.                 {
  721.                     //Clear old connections
  722.                     for(int i=0;i<8;i++)
  723.                         tile->m_pNeighbors[i] = NULL;
  724.  
  725.                     //Possible neighbors
  726.                     INTPOINT p[] = {INTPOINT(x-1, y-1), INTPOINT(x, y-1), INTPOINT(x+1, y-1),
  727.                                     INTPOINT(x-1, y),                      INTPOINT(x+1, y),
  728.                                     INTPOINT(x-1, y+1), INTPOINT(x, y+1), INTPOINT(x+1, y+1)};
  729.  
  730.                     //For each neighbor
  731.                     for(int i=0;i<8;i++)    
  732.                         if(Within(p[i]))
  733.                         {
  734.                             MAPTILE *neighbor = GetTile(p[i]);
  735.  
  736.                             //Connect tiles if the neighbor is m_walkable
  737.                             if(neighbor != NULL && neighbor->m_walkable)
  738.                                 tile->m_pNeighbors[i] = neighbor;
  739.                         }
  740.                 }
  741.             }
  742.  
  743.         CreateTileSets();
  744.     }
  745.     catch(...)
  746.     {
  747.         debug.Print("Error in InitPathfinding()");
  748.     }    
  749. }
  750.  
  751. void TERRAIN::UpdatePathfinding(RECT *r)
  752. {
  753.     if(r == NULL)
  754.     {
  755.         InitPathfinding();
  756.         return;
  757.     }
  758.  
  759.     //Connect maptiles using the neightbors[] pointers
  760.     for(int y=r->top; y<=r->bottom; y++)        
  761.         for(int x=r->left; x<=r->right; x++)
  762.         {
  763.             MAPTILE *tile = GetTile(x, y);
  764.             if(tile != NULL && tile->m_walkable)
  765.             {
  766.                 //Clear old connections
  767.                 for(int i=0;i<8;i++)
  768.                     tile->m_pNeighbors[i] = NULL;
  769.  
  770.                 //Possible neighbors
  771.                 INTPOINT p[] = {INTPOINT(x-1, y-1), INTPOINT(x, y-1), INTPOINT(x+1, y-1),
  772.                                 INTPOINT(x-1, y),                      INTPOINT(x+1, y),
  773.                                 INTPOINT(x-1, y+1), INTPOINT(x, y+1), INTPOINT(x+1, y+1)};
  774.  
  775.                 //For each neighbor
  776.                 for(int i=0;i<8;i++)
  777.                     if(Within(p[i]))
  778.                     {
  779.                         MAPTILE *neighbor = GetTile(p[i]);
  780.  
  781.                         //Connect tiles if the neighbor is walkable
  782.                         if(neighbor != NULL && neighbor->m_walkable)
  783.                             tile->m_pNeighbors[i] = neighbor;
  784.                     }
  785.             }
  786.         }
  787.  
  788.     CreateTileSets();
  789. }
  790.  
  791. void TERRAIN::CreateTileSets()
  792. {
  793.     try
  794.     {
  795.         int setNo = 0;
  796.         for(int y=0;y<m_size.y;y++)        //Set a unique m_set for each tile...
  797.             for(int x=0;x<m_size.x;x++)
  798.                 m_pMapTiles[x + y * m_size.x].m_set = setNo++;
  799.  
  800.         bool changed = true;
  801.         while(changed)
  802.         {
  803.             changed = false;
  804.  
  805.             for(int y=0;y<m_size.y;y++)
  806.                 for(int x=0;x<m_size.x;x++)
  807.                 {
  808.                     MAPTILE *tile = GetTile(x, y);
  809.  
  810.                     //Find the lowest m_set of a neighbor
  811.                     if(tile != NULL && tile->m_walkable)
  812.                     {
  813.                         for(int i=0;i<8;i++)
  814.                             if(tile->m_pNeighbors[i] != NULL &&
  815.                                 tile->m_pNeighbors[i]->m_walkable &&
  816.                                 tile->m_pNeighbors[i]->m_set < tile->m_set)
  817.                             {
  818.                                 changed = true;
  819.                                 tile->m_set = tile->m_pNeighbors[i]->m_set;
  820.                             }
  821.                     }
  822.                 }
  823.         }
  824.     }
  825.     catch(...)
  826.     {
  827.         debug.Print("Error in TERRAIN::CreateTileSets()");
  828.     }
  829. }
  830.  
  831. float H(INTPOINT a, INTPOINT b)
  832. {
  833.     //return abs(a.x - b.x) + abs(a.y - b.y);
  834.     return a.Distance(b);
  835. }
  836.  
  837. std::vector<INTPOINT> TERRAIN::GetPath(INTPOINT start, INTPOINT goal, bool considerUnits)
  838. {
  839.     try
  840.     {
  841.         //Check that the two points are within the bounds of the map
  842.         MAPTILE *startTile = GetTile(start);
  843.         MAPTILE *goalTile = GetTile(goal);
  844.  
  845.         if(!Within(start) || !Within(goal) || start == goal || startTile == NULL || goalTile == NULL)
  846.             return std::vector<INTPOINT>();
  847.  
  848.         //Check if a path exists
  849.         if(!startTile->m_walkable || !goalTile->m_walkable || startTile->m_set != goalTile->m_set)
  850.             return std::vector<INTPOINT>();
  851.  
  852.         //Init Search
  853.         long numTiles = m_size.x * m_size.y;
  854.         for(long l=0;l<numTiles;l++)
  855.         {
  856.             m_pMapTiles[l].f = m_pMapTiles[l].g = INT_MAX;        //Clear F,G
  857.             m_pMapTiles[l].open = m_pMapTiles[l].closed = false;    //Reset Open and Closed
  858.         }
  859.  
  860.         std::vector<MAPTILE*> open;                //Create Our Open list
  861.         startTile->g = 0;                        //Init our starting point (SP)
  862.         startTile->f = H(start, goal);
  863.         startTile->open = true;
  864.         open.push_back(startTile);                //Add SP to the Open list
  865.  
  866.         bool found = false;                    // Search as long as a path hasnt been found,
  867.         while(!found && !open.empty())        // or there is no more tiles to search
  868.         {                                                
  869.             MAPTILE * best = open[0];        // Find the best tile (i.e. the lowest F value)
  870.             int bestPlace = 0;
  871.             for(int i=1;i<open.size();i++)
  872.                 if(open[i]->f < best->f)
  873.                 {
  874.                     best = open[i];
  875.                     bestPlace = i;
  876.                 }
  877.             
  878.             if(best == NULL)break;            //No path found
  879.  
  880.             open[bestPlace]->open = false;
  881.             open.erase(&open[bestPlace]);    // Take the best node out of the Open list
  882.  
  883.             if(best->mappos == goal)        //If the goal has been found
  884.             {
  885.                 std::vector<INTPOINT> p, p2;
  886.                 MAPTILE *point = best;
  887.  
  888.                 while(point->mappos != start)    // Generate path
  889.                 {
  890.                     p.push_back(point->mappos);
  891.                     point = point->m_pParent;
  892.  
  893.                     if(p.size() > 500)        //Too long path, something is wrong
  894.                         return std::vector<INTPOINT>();
  895.                 }
  896.  
  897.                 for(int i=p.size()-1;i!=0;i--)    // Reverse path
  898.                     p2.push_back(p[i]);
  899.                 p2.push_back(goal);
  900.                 return p2;
  901.             }
  902.             else
  903.             {
  904.                 for(i=0;i<8;i++)                    // otherwise, check the neighbors of the
  905.                     if(best->m_pNeighbors[i] != NULL)    // best tile
  906.                         if(!considerUnits || best->m_pNeighbors[i]->m_pMapObject == NULL)
  907.                         {
  908.                             bool inList = false;        // Generate new G and F value
  909.                             float newG = best->g + 1.0f;
  910.                             float d = H(best->mappos, best->m_pNeighbors[i]->mappos);
  911.                             float newF = newG + H(best->m_pNeighbors[i]->mappos, goal) + best->m_pNeighbors[i]->m_cost * 5.0f * d;
  912.  
  913.                             if(best->m_pNeighbors[i]->open || best->m_pNeighbors[i]->closed)
  914.                             {
  915.                                 if(newF < best->m_pNeighbors[i]->f)    // If the new F value is lower
  916.                                 {
  917.                                     best->m_pNeighbors[i]->g = newG;    // update the values of this tile
  918.                                     best->m_pNeighbors[i]->f = newF;
  919.                                     best->m_pNeighbors[i]->m_pParent = best;                                
  920.                                 }
  921.                                 inList = true;
  922.                             }
  923.  
  924.                             if(!inList)            // If the neighbor tile isn't in the Open or Closed list
  925.                             {
  926.                                 best->m_pNeighbors[i]->f = newF;        //Set the values
  927.                                 best->m_pNeighbors[i]->g = newG;
  928.                                 best->m_pNeighbors[i]->m_pParent = best;
  929.                                 best->m_pNeighbors[i]->open = true;
  930.                                 open.push_back(best->m_pNeighbors[i]);    //Add it to the open list    
  931.                             }
  932.                         }
  933.  
  934.                 best->closed = true;        //The best tile has now been searched, add it to the Closed list
  935.             }
  936.         }
  937.  
  938.         return std::vector<INTPOINT>();        //No path found, return an empty path
  939.         
  940.     }
  941.     catch(...)
  942.     {
  943.         debug.Print("Error in TERRAIN::GetPath()");
  944.         return std::vector<INTPOINT>();
  945.     }
  946. }
  947.  
  948. MAPTILE* TERRAIN::GetTile(int x, int y)
  949. {
  950.     if(m_pMapTiles == NULL)return NULL;
  951.  
  952.     try
  953.     {
  954.         if(Within(INTPOINT(x, y)))
  955.             return &m_pMapTiles[x + y * m_size.x];
  956.         else return NULL;
  957.     }
  958.     catch(...)
  959.     {
  960.         return NULL;
  961.     }
  962. }
  963.  
  964. void TERRAIN::SaveTerrain(char fileName[])
  965. {
  966.     try
  967.     {
  968.         std::ofstream out(fileName, std::ios::binary);        //Binary format
  969.  
  970.         if(out.good())
  971.         {
  972.             out.write((char*)&m_size, sizeof(INTPOINT));    //Write map size
  973.  
  974.             //Write all the maptile information needed to recreate the map
  975.             for(int y=0;y<m_size.y;y++)
  976.                 for(int x=0;x<m_size.x;x++)
  977.                 {
  978.                     MAPTILE *tile = GetTile(x, y);
  979.                     out.write((char*)&tile->m_type, sizeof(int));            //type
  980.                     out.write((char*)&tile->m_height, sizeof(float));        //Height
  981.                 }
  982.  
  983.             //Write all the objects
  984.             int numObjects = m_objects.size();
  985.             out.write((char*)&numObjects, sizeof(int));     //Num Objects
  986.             for(int i=0;i<m_objects.size();i++)
  987.             {
  988.                 out.write((char*)&m_objects[i].m_type, sizeof(int));                //type
  989.                 out.write((char*)&m_objects[i].m_mappos, sizeof(INTPOINT));            //mappos
  990.                 out.write((char*)&m_objects[i].m_meshInstance.m_pos, sizeof(D3DXVECTOR3));    //Pos
  991.                 out.write((char*)&m_objects[i].m_meshInstance.m_rot, sizeof(D3DXVECTOR3));    //Rot
  992.                 out.write((char*)&m_objects[i].m_meshInstance.m_sca, sizeof(D3DXVECTOR3));    //Sca
  993.             }
  994.         }
  995.  
  996.         out.close();
  997.     }
  998.     catch(...)
  999.     {
  1000.         debug.Print("Error in TERRAIN::SaveTerrain()");
  1001.     }
  1002. }
  1003.  
  1004. void TERRAIN::LoadTerrain(char fileName[])
  1005. {
  1006.     try
  1007.     {
  1008.         std::ifstream in(fileName, std::ios::binary);        //Binary format
  1009.  
  1010.         if(in.good())
  1011.         {
  1012.             Release();    //Release all terrain resources
  1013.  
  1014.             in.read((char*)&m_size, sizeof(INTPOINT));    //read map size
  1015.         
  1016.             if(m_pMapTiles != NULL)    //Clear old maptiles
  1017.                 delete [] m_pMapTiles;
  1018.  
  1019.             //Create new m_pMapTiles
  1020.             m_pMapTiles = new MAPTILE[m_size.x * m_size.y];
  1021.             memset(m_pMapTiles, 0, sizeof(MAPTILE)*m_size.x*m_size.y);
  1022.  
  1023.  
  1024.             //Read the maptile information
  1025.             for(int y=0;y<m_size.y;y++)
  1026.                 for(int x=0;x<m_size.x;x++)
  1027.                 {
  1028.                     MAPTILE *tile = GetTile(x, y);
  1029.                     in.read((char*)&tile->m_type, sizeof(int));            //type
  1030.                     in.read((char*)&tile->m_height, sizeof(float));        //Height
  1031.                 }
  1032.  
  1033.             //Read number of objects
  1034.             int numObjects = 0;
  1035.             in.read((char*)&numObjects, sizeof(int));
  1036.             for(int i=0;i<numObjects;i++)
  1037.             {
  1038.                 int type = 0;
  1039.                 INTPOINT mp;
  1040.                 D3DXVECTOR3 p, r, s;
  1041.  
  1042.                 in.read((char*)&type, sizeof(int));            //type
  1043.                 in.read((char*)&mp, sizeof(INTPOINT));        //mappos
  1044.                 in.read((char*)&p, sizeof(D3DXVECTOR3));    //Pos
  1045.                 in.read((char*)&r, sizeof(D3DXVECTOR3));    //Rot
  1046.                 in.read((char*)&s, sizeof(D3DXVECTOR3));    //Sca
  1047.  
  1048.                 m_objects.push_back(OBJECT(type, mp, p, r, s));
  1049.             }
  1050.  
  1051.             //Recreate Terrain
  1052.             InitPathfinding();
  1053.             CreatePatches(3);
  1054.             CalculateAlphaMaps();
  1055.             CalculateLightMap(true);
  1056.         }
  1057.  
  1058.         in.close();
  1059.     }
  1060.     catch(...)
  1061.     {
  1062.         debug.Print("Error in TERRAIN::LoadTerrain()");
  1063.     }
  1064. }
  1065.  
  1066. D3DXVECTOR3 TERRAIN::GetWorldPos(INTPOINT mappos)
  1067. {
  1068.     if(!Within(mappos))return D3DXVECTOR3(0, 0, 0);
  1069.     MAPTILE *tile = GetTile(mappos);
  1070.     return D3DXVECTOR3(mappos.x, tile->m_height, -mappos.y);
  1071. }
  1072.  
  1073. INTPOINT TERRAIN::GetClosestFreeTile(INTPOINT to, INTPOINT from)
  1074. {
  1075.     for(int i=0;i<5;i++)    //Search radius
  1076.     {
  1077.         std::vector<MAPTILE*> tiles;
  1078.  
  1079.         //Get tiles in current search radius
  1080.         for(int y=to.y - i;y<=to.y + i;y++)
  1081.         {
  1082.             tiles.push_back(GetTile(to.x - i, y));
  1083.             tiles.push_back(GetTile(to.x + i, y));
  1084.         }
  1085.  
  1086.         for(int x=to.x - i + 1;x<=to.x + i - 1;x++)
  1087.         {
  1088.             tiles.push_back(GetTile(x, to.y - i));
  1089.             tiles.push_back(GetTile(x, to.y + i));
  1090.         }
  1091.  
  1092.         //Find closest tile...
  1093.         MAPTILE *closest = NULL;
  1094.         float dist = 10000.0f;
  1095.  
  1096.         for(int t=0;t<tiles.size();t++)
  1097.             if(tiles[t] != NULL)
  1098.                 if(tiles[t]->m_walkable && tiles[t]->m_pMapObject == NULL)
  1099.                 {
  1100.                     float d = from.Distance(tiles[t]->mappos);
  1101.                     if(d < dist)
  1102.                     {
  1103.                         dist = d;
  1104.                         closest = tiles[t];
  1105.                     }
  1106.                 }
  1107.  
  1108.         if(closest != NULL)
  1109.             return closest->mappos;
  1110.     }
  1111.  
  1112.     return to;
  1113. }